package com.yc.leetcode;

import javafx.beans.binding.StringBinding;

import java.math.BigDecimal;
import java.util.*;

/**
 * N皇后问题
 */
public class Nqueen {
    public static void main(String[] args) {
        Nqueen n = new Nqueen();
//        n.test();
//        System.out.println(n.climbStairs(24));
        n.m1();
    }

    public void test() {
//        Math.abs()
//        Arrays.fill();
        System.out.println(factorial(4, 2));
        char[] a = new char[2];
        String aaa = new String(a);
//        Queue<Integer> queue = new LinkedList<>();
        Queue<Integer> queue = new PriorityQueue<>();
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        List<String> ss = new ArrayList<>();
        Iterator<Character> iter = stack.iterator();
        ArrayDeque<Integer> q = new ArrayDeque();

    }



    public int climbStairs(int n) {
        System.out.println("Integer.MAX_VALUE=" + Integer.MAX_VALUE);
        int sum = 0;
        //当有0个2，只有一种可能
        sum++;
        for (int i=1; i<=n/2; i++) {//i个2
            sum += factorial_b(n-i, n-2*i+1).divide(factorial_b(i,1)).intValue();
        }
        return sum;
    }

    /**
     * 阶乘
     * @param n
     * @param min
     * @return
     */
    public int factorial(int n, int min) {
        if (n < min) {
            return -1;
        }
        if (min <= 0) {
            return -2;
        }
        if (n == min) {
            return n;
        } else {
            int res = n*factorial(n-1, min);
            System.out.println(res);
            return res;
        }
    }

    public BigDecimal factorial_b(int n, int min) {
        if (n < min) {
            return new BigDecimal(-1);
        }
        if (min <= 0) {
            return new BigDecimal(-2);
        }
        if (n == min) {
            return new BigDecimal(n);
        } else {
            return new BigDecimal(n).multiply(factorial_b(n-1, min));
        }
    }

    public void m1() {
//        String senate = "DRRDRDRDRDDRDRDR";
        String senate = "RDD";
//        System.out.println(predictPartyVictory(senate));
//        System.out.println(predictPartyVictory2(senate));
        System.out.println(predictPartyVictory3(senate));
    }

    public String predictPartyVictory(String senate) {
        int[][] c = new int[2][2];
        int index = 0;
        int first = (senate.charAt(0) == 'R')?0:1;//前面的

        for (int i=0; i<senate.length(); i++) {
            index = (senate.charAt(i) == 'R')?0:1;
            if (c[index^1][1] > 0) {//被干掉
                c[index^1][1]--;//对方弹药-1
            } else {//对方无弹药，反过来 试图干掉对方中的一个
                if (c[index^1][0] > 0) {//对方有人
                    c[index^1][0]--;//对方-1
                    c[index][0]++;//自己入队，但已无弹药
                } else {//对方没人
                    first = index;//前后顺序改变
                    c[index][0]++;//自己入队
                    c[index][1]++;//弹药+1
                }
            }
        }

        // while (c[0][0] > 0 && c[1][0] > 0) {//双方还有人，继续作战
        //     c[0][1] = c[0][0];
        //     c[1][1] = c[1][0];

        // }
        if (c[0][0] > c[1][0]) {
            return "Radiant";
        } else if (c[0][0] == c[1][0]) {
            return (first==0)?"Radiant":"Dire";
        } else {
            return "Dire";
        }

    }


    public String predictPartyVictory2(String senate) {
        int n = senate.length();
        Queue<Integer> radiant = new LinkedList<Integer>();
        Queue<Integer> dire = new LinkedList<Integer>();
        for (int i = 0; i < n; ++i) {
            if (senate.charAt(i) == 'R') {
                radiant.offer(i);
            } else {
                dire.offer(i);
            }
        }
        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int radiantIndex = radiant.poll(), direIndex = dire.poll();
            if (radiantIndex < direIndex) {
                radiant.offer(radiantIndex + n);
            } else {
                dire.offer(direIndex + n);
            }
        }
        return !radiant.isEmpty() ? "Radiant" : "Dire";
    }

    public String predictPartyVictory3(String senateStr) {
        // R = true表示本轮循环结束后，字符串里依然有R。D同理
        Boolean R = true, D = true;
        // 当flag大于0时，R在D前出现，R可以消灭D。当flag小于0时，D在R前出现，D可以消灭R
        int flag = 0;
        byte[] senate =  senateStr.getBytes();
        while (R && D) { // 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了
            R = false;
            D = false;
            for (int i = 0; i < senate.length; i++) {
                if (senate[i] == 'R') {
                    if (flag < 0) senate[i] = 0; // 消灭R，R此时为false
                    else R = true; // 如果没被消灭，本轮循环结束有R
                    flag++;
                }
                if (senate[i] == 'D') {
                    if (flag > 0) senate[i] = 0;
                    else D = true;
                    flag--;
                }
            }
        }
        // 循环结束之后，R和D只能有一个为true
        return R == true ? "Radiant" : "Dire";
    }
}
